//
//  Vector_uniquify.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 有序向量去重
extension Vector where Element: Comparable {
    
    public func uniquify() -> Int {
        #if false
        if _size <= 1 { return 0 }
        let oldSize = _size
        var sameElementStartIndex = startIndex
        var sameElementEndIndex = startIndex + 1
        while sameElementEndIndex < endIndex {
            if _storage[sameElementEndIndex] == _storage[sameElementStartIndex] {
                sameElementEndIndex += 1
            } else {
                sameElementStartIndex += 1
                remove(at: sameElementStartIndex..<sameElementEndIndex)
                sameElementEndIndex = sameElementStartIndex + 1
            }
        }
        /// 最后一轮
        if sameElementStartIndex + 1 != endIndex {
            remove(at: (sameElementStartIndex + 1)..<endIndex)
        }
        return oldSize - _size
        #else
        if _size <= 1 { return 0 }
        var uniqueEndIndex = startIndex
        var offset = startIndex + 1
        while offset < endIndex {
            if _storage[offset] != _storage[uniqueEndIndex] {
                // 并不真正删除元素
                // 向量可访问区间由_size控制
                uniqueEndIndex += 1
                _storage[uniqueEndIndex] = _storage[offset]
            }
            offset += 1
        }
        _size = uniqueEndIndex + 1
        _shrink()
        return offset - uniqueEndIndex - 1
        #endif
    }
}
